Estetyczny tekst

Limit pamięci: 128 MB

Rozważmy dowolny tekst złożony z słów ponumerowanych od do . Dowolny podział tego tekstu na wierszy reprezentujemy za pomocą takiego ciągu liczb , że słowa o numerach od do znajdują się w pierwszym wierszu, słowa o numerach od do znajdują się w drugim wierszu itd., a słowa o numerach od do znajdują się w ostatnim, -tym wierszu.

Każde słowo ma określoną długość (wyrażoną liczbą znaków). Długość słowa o numerze oznaczamy przez . Ponadto każde dwa sąsiednie słowa w wierszu są oddzielone odstępem szerokości jednego znaku. Długością wiersza nazywamy sumę długości wszystkich słów w tym wierszu powiększoną o liczbę odstępów między nimi. Długość wiersza o numerze oznaczamy przez . Oznacza to, że jeżeli w wierszu o numerze znajdują się słowa o numerach od do włącznie, to długość tego wiersza wynosi:

Dla przykładu, rozważmy tekst złożony z słów o długościach kolejno , , i oraz jego podział na wiersze. Wówczas długość pierwszego wiersza wynosi , drugiego - , a trzeciego - :

Współczynnikiem estetyczności podziału danego tekstu na wierszy nazywamy liczbę wyrażoną wzorem:

W szczególności, jeżeli podział zajmuje tylko jeden wiersz, jego współczynnik estetyczności jest równy .

Im mniejszy jest współczynnik estetyczności, tym bardziej estetyczny jest dany podział. Rozpatrujemy tylko takie podziały, w których długość żadnego wiersza nie przekracza pewnej stałej liczby . Spośród wszystkich takich podziałów danego tekstu na dowolną liczbę wierszy poszukujemy podziału najbardziej estetycznego, czyli o minimalnym współczynniku estetyczności. W podanym powyżej przykładzie współczynnik estetyczności podziału jest równy i jest to minimalna wartość współczynnika estetyczności dla lub .

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia liczby i oraz długości kolejnych słów,
• wyznaczy minimalny współczynnik estetyczności dla tych podziałów, w których długość żadnego wiersza nie przekracza ,
• wypisze wynik na standardowe wyjście.

Wejście

Pierwszy wiersz standardowego wejścia zawiera liczby całkowite i , , , oddzielone pojedynczym odstępem. Drugi i ostatni wiersz wejścia zawiera liczb całkowitych będących długościami kolejnych słów, dla , pooddzielanych pojedynczymi odstępami.

Wyjście

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą: minimalny współczynnik estetyczności dla tych podziałów, w których długość żadnego wiersza nie przekracza .

Przykład

Dla danych wejściowych:

6 4
4 3 2 5

poprawnym wynikiem jest:

3

a dla danych wejściowych:

4 2
1 2

poprawnym wynikiem jest:

0

Autor zadania: Bartosz Walczak.